#include <iostream>
#include <vector>
/* 
 * 找到中位数
问题：如何在不完全排序的情况下求数组中的中位数？

奇数： N/2
偶数： N/2  N+1/2 

 */

// 1. 暴力法

// 10  11  32   55  77
// 2  3 5 10 23 67


// 快排：
// 1. 找基准
// 2. 分拨 A B
// 3. A 重复 1 2   
 








int Paritition1(std::vector<int>& arr, int low, int high) {
	int pivot = arr[low];
	while (low < high) {
		while (low < high && arr[high] >= pivot) {
			--high;
		}
		arr[low] = arr[high];

		while (low < high && arr[low] <= pivot) {
			++low;
		}
		arr[high] = arr[low];
	}

	arr[low] = pivot;
	return low;
}

void QuickSort(std::vector<int>& arr, int low, int high, int midIndex) 
{
	if (low < high) {
		int pivot = Paritition1(arr, low, high);
		QuickSort(arr, low, pivot - 1, midIndex);
	//	QuickSort(arr, pivot + 1, high, midIndex);
		 if(pivot <= midIndex ) {
		 	QuickSort(arr, pivot + 1, high, midIndex);
		 }
		
	}
}

int getmid(std::vector<int>& vctNums) {
	if (vctNums.size() < 1)
	{
		return -1;
	}

	if (vctNums.size() == 1)
	{
		return vctNums[0];
	}

	if (vctNums.size() == 2)
	{
		return (vctNums[0] + vctNums[1]) / 2;
	}

	QuickSort(vctNums, 0, vctNums.size() - 1, vctNums.size() / 2);
	if (vctNums.size() %2 == 0)
	{
		int n = vctNums.size() / 2;
		return (vctNums[n] + vctNums[n-1]) / 2;
	}
	else {
		int n = vctNums.size() / 2;
		return vctNums[n];
	}
	
}

int main() {

	std::vector<int> nums{ 9, 6, 6, 1, 4,3,6,1, 7,8, 7};
	std::vector<int> nu{1, 6, 6, 1, 4, 3, 6, 7, 7, 8, 9};

	auto getter = getmid(nu);
	for(auto i : nu) {
		std::cout << i << ' ';
	}
	std::cout << '\n';
	std::cout << getter << std::endl;
}